1782F - Bracket Insertion - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
using LL = long long;


class ModulusInt
{
private:
    static const int MOD = 998244353;
    int val; // RI: 0 <= val < MOD
public: // Constructors
    ModulusInt(): val(0) {}
    ModulusInt(int v): val(v % MOD)
    {
        if(val < 0) val += MOD;
    }
    ModulusInt(long long v): val(v % MOD)
    {
        if(val < 0) val += MOD;
    }
public:
    operator int() const {return val;}
    int getValue() const {return val;}
public:
    // Comparison (Congruence)
    bool operator ==(const ModulusInt & that) const {return val == that.val;}
    bool operator !=(const ModulusInt & that) const {return val != that.val;}
public: // Arithmetic Operations
    ModulusInt & operator += (const ModulusInt &that)
    {
        val += that.val;
        if(val >= MOD) val -= MOD;
        return *this;
    }

    ModulusInt & operator -= (const ModulusInt &that)
    {
        val += MOD - that.val;
        if(val >= MOD) val -= MOD;
        return *this;
    }

    ModulusInt & operator *= (const ModulusInt &that)
    {
        long long v = (long long) val * (long long) that.val;
        val = (int) (v % MOD);
        return *this;
    }

    // The behavior is undefined if the modular inverse does not exist
    ModulusInt & operator /= (const ModulusInt &that)
    {
        ModulusInt inv = getModularInverse(that.val, MOD);
        *this *= inv;
        return *this;
    }
public:
    ModulusInt operator + (const ModulusInt &that) const {return ModulusInt(*this) += that;}
    ModulusInt operator - (const ModulusInt &that) const {return ModulusInt(*this) -= that;}
    ModulusInt operator * (const ModulusInt &that) const {return ModulusInt(*this) *= that;}
    ModulusInt operator / (const ModulusInt &that) const {return ModulusInt(*this) /= that;}

    ModulusInt operator + (const int &v) const {return ModulusInt(*this) += ModulusInt(v);}
    ModulusInt operator - (const int &v) const {return ModulusInt(*this) -= ModulusInt(v);}
    ModulusInt operator * (const int &v) const {return ModulusInt(*this) *= ModulusInt(v);}
    ModulusInt operator / (const int &v) const {return ModulusInt(*this) /= ModulusInt(v);}

    ModulusInt operator + (const long long &v) const {return ModulusInt(*this) += ModulusInt(v);}
    ModulusInt operator - (const long long &v) const {return ModulusInt(*this) -= ModulusInt(v);}
    ModulusInt operator * (const long long &v) const {return ModulusInt(*this) *= ModulusInt(v);}
    ModulusInt operator / (const long long &v) const {return ModulusInt(*this) /= ModulusInt(v);}

public: // Non-Basic Arithmetic Operations
    static ModulusInt getPower(ModulusInt a, int p)
    {
        if(p == 0) return 1;
        if(p == 1) return a;
        ModulusInt h = getPower(a, p/2);
        h *= h;
        if(p & 1) {h *= a;}
        return h;
    }

    static ModulusInt factorial(int n)
    {
        ModulusInt ret = 1;
        for(int i=1;i<=n;i++) ret *= i;
        return ret;
    }
private:
    static void gcd(int a,int b,int &v1,int &v2,int &g)  // g = v1 * a + v2 * b where g = gcd(a,b)
    {
        int q = a/b;
        int r = a - q * b;
        if(r == 0)
        {
            g = b; v1 = 0; v2 = 1; return;
        }
        // Task: (v1,v2) = (v2,v1- v2*q)
        gcd(b,r,v2,v1,g);
        v2 -= v1*q;
    }

    // Return a multiplicative modular inverse of a (mod m)
    // Assume gcd(a,m) = 1
    static int getModularInverse(int a,int m)  // Return s where s * a = 1 (mod m)
    {
        int v1,v2,g;
        gcd(a,m,v1,v2,g); // assert(g == 1);
        v1 %= m;
        if(v1<0) v1 += m;
        return v1;
    }
};


// ---------------------------------------------

int n;
int q;
ModulusInt P;
ModulusInt Q;

const int MXN = 512;
ModulusInt spreadProb[MXN][MXN];
ModulusInt dp[MXN][MXN];


int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> q;
    P = ModulusInt(q);  P /= 10000;
    Q = ModulusInt(1) - P;

    // Part 1: Spread Probability
    spreadProb[1][0] = 1;

    for(int i = 2; i <= n; i++)
    {
        // New Pair
        spreadProb[i][0] = 1;
        // Old Pair
        for(int j = 0; j < i; j++)
        {
            // Case 1: Extension
            if(j > 0) spreadProb[i][j] += spreadProb[i - 1][j - 1] * ModulusInt(2 * j - 1);
            // Case 2: Stay the same (outside)
            spreadProb[i][j] += spreadProb[i - 1][j] * ModulusInt(2 * (i - j) - 3);

            // Common denominator
            spreadProb[i][j] /= ModulusInt(2 * i - 1);
            // fprintf(stderr,"g[%d][%d] = %d\n", i, j, spreadProb[i][j].getValue());
        }
    }

    // Part 2: The answer
    for(int s = 0; s <= n; s++) dp[0][s] = 1;

    for(int i = 1; i <= n; i++)
    {
        for(int s = 0; s <= i; s++)
        {
            for(int k = 0; k < i; k++)
            {
                // Case 1: ()
                ModulusInt c1 = P * dp[k][s + 1] * dp[i - k - 1][s];
                // Case 2: )(
                ModulusInt c2 = 0;
                if(s > 0) c2 = Q * dp[k][s - 1] * dp[i - k - 1][s];

                dp[i][s] += spreadProb[i][k] * (c1 + c2);
            }
        }

        for(int s = i + 1; s <= n; s++) dp[i][s] = 1;

    }

    cout << dp[n][0].getValue() << "\n";
    return 0;
}